package com.wangp.mywrite.coding;

import java.util.Arrays;

/**
 * @author tooStrongerW
 * @version 1.0
 * @date 2021/3/31 20:01
 */
public class MergeSort extends Sort {

    public static void main(String[] args) {
        // 随机生成数组
        int[] arr = genRandomArr(19);
        // 排序
        mergeSort(arr);
        // 验证顺序
        checkArrOrder(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr) {
        // 创建临时数组，存放数组
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int low, int high) {
        // 递归终止条件
        if (low < high) {
            int mid = (high + low) / 2;
            // 拆左子序列
            mergeSort(arr, low, mid);
            // 拆右子序列
            mergeSort(arr, mid + 1, high);
            // 合并
            int[] tmp = new int[arr.length];
            merge(arr, low, mid, high, tmp);
        }
    }

    private static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
        int i = 0, j = low, k = mid + 1;
        // 将序列区间内有序存入tmp数组
        while (j <= mid && k <= high) {
            // 如果[low,mid] 比 (mid,high] 小，存入tmp数组
            if (arr[j] < arr[k]) {
                tmp[i++] = arr[j++];
            } else {
                tmp[i++] = arr[k++];
            }
        }
        // 若[low,mid]有剩余元素，继续添加
        while (j <= mid) {
            tmp[i++] =   arr[j++];
        }
        // 若(mid,high]有剩余元素，继续添加
        while (k <= high) {
            tmp[i++] = arr[k++];
        }
        // 将tmp数组复制到arr中完成这[low.high]排序
        for (int t = 0; t < i; t++) {
            arr[low + t] = tmp[t];
        }
    }
}
